home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 10 - 1994 / 10.02 Feb 94 / Programmers' Challenge / PackPresents.c.orig next >
Encoding:
Text File  |  1995-07-29  |  17.0 KB  |  592 lines  |  [TEXT/KAHL]

  1. /*======================================================
  2.         PackPresents()
  3.     
  4.         Clement James Goebel III.
  5.         Programmers Challenge Dec 93 issue
  6.         
  7.   ------------------------------------------------------
  8.       This code accepts a number of presents one after 
  9.       another and attempts to store as MANY as possible
  10.       in its storage area.  This routine starts with an
  11.       array describing the expected distribution of data
  12.       and then slowly changes to use an array that 
  13.       describes the sizes of observed presents as the 
  14.       process continues.  These arrays are used to decide
  15.       which presents are too big and should not be 
  16.       stored as they will cause us to throw away smaller
  17.       presents latter.  The routine is slow and methodical
  18.       as it trys to pack presents into the smallest 
  19.       spaces it can find.  It also does an ok job of
  20.       guessing which packages to discard, a function
  21.       that might not really be needed with evenly 
  22.       distributed data sets.  But the goal was to pack the
  23.       most, so you can't be too careful.
  24.       
  25.       The matrix that keeps track of stored presents
  26.       contains zeros where presents are stored, and all
  27.       other locations contain a value that represents the
  28.       amount of free space that is contiguous to that
  29.       location.  We will always try to fill small holes
  30.       first, a better way might be to look for presents
  31.       that are half the size of the hole, but that would
  32.       require many more special cases.  And when placing
  33.       presents we will always try to get as many surfaces
  34.       to touch as possible.
  35.   ------------------------------------------------------*/
  36.   
  37. #include "stdio.h"
  38.  
  39. #define PRINTF    0    /* display debug info */
  40.  
  41. #define WID_DIM                100
  42. #define LEN_DIM                100
  43.  
  44. #define    MIN_GIFT_DIM        5
  45. #define MAX_GIFT_DIM        15
  46.  
  47. #define LIKES_OTHERS        3
  48. #define LIKES_WALLS            2
  49.  
  50. #define SPACE_USED            0
  51. #define MEASURING            -1
  52.  
  53. static short sgsGiftsSeen;
  54. static short sgsGiftsStored;
  55. static long  sglExpectedCount;
  56. static short sgsLeftmostPresent;
  57. static short sgsTopmostPresent;
  58. static long     sglItemsOnStack;
  59. static long     sglTotalAreaExpected;
  60. static short *sgasStack;
  61. static short *sgasAreasSeen;
  62. static short *sgasAreasExpected;
  63. static long  *sgalSpace;
  64.  
  65. /*------------------------------------------------------
  66.     Function defs.  User calls PackPresents
  67.   ------------------------------------------------------*/
  68. typedef void (*NextPresProc)
  69.     (unsigned short *pWidth, unsigned short *pLength );
  70. typedef void (*StorePresProc)
  71.             (unsigned short xPos, unsigned short yPos );
  72.  
  73. void PackPresents( unsigned short usNumGifts,
  74.                     NextPresProc pNextPresProc,
  75.                     StorePresProc pStorePresProc );
  76.  
  77. void MyPacker( unsigned short usNumGifts,
  78.                     long sgaalStorage[WID_DIM][LEN_DIM],
  79.                     NextPresProc pNextPresProc,
  80.                     StorePresProc pStorePresProc );
  81.  
  82. /*======================================================
  83.         PackPresents()
  84.     
  85.     Sets up memory and other yukky stuff before calling
  86.     routine to actually do the work.
  87.   ------------------------------------------------------*/
  88. void PackPresents( unsigned short usNumGifts,
  89.                     NextPresProc pNextPresProc,
  90.                     StorePresProc pStorePresProc )
  91. {
  92.     long w, l;
  93.     long lBytes;
  94.     
  95.     sgsGiftsSeen = 0;
  96.     sgsGiftsStored = 0;
  97.     sglItemsOnStack = 0;
  98.     sgsLeftmostPresent = WID_DIM;
  99.     sgsTopmostPresent = LEN_DIM;
  100.     
  101.     lBytes = (MAX_GIFT_DIM+1) 
  102.                 * (MAX_GIFT_DIM+1) * sizeof( short );
  103.     sgasAreasSeen = (void*)NewPtrClear( lBytes );
  104.     sgasAreasExpected = (void*)NewPtrClear( lBytes );
  105.     sgasStack = (void*)NewPtrClear( (WID_DIM * LEN_DIM ) 
  106.                                 * 2 * sizeof( short ) );
  107.     sgalSpace = (void*)NewPtrClear( WID_DIM * LEN_DIM 
  108.                                 * sizeof( long ) );
  109.     
  110.     if ( sgasStack == NULL || sgalSpace == NULL  
  111.                     || sgasAreasExpected == NULL 
  112.                     || sgasAreasSeen == NULL )
  113.         DebugStr("\pMemory Allocations Failed" );
  114.         
  115. /*------------------------------------------------------
  116.     Given the range of inputs we expect to see compute
  117.     the number of presents of each size that we 
  118.     expect to be offered.
  119.   ------------------------------------------------------*/
  120.     sgsGiftsSeen = 0;
  121.     sglExpectedCount = 0;
  122.     sglTotalAreaExpected = 0;
  123.     for ( w = MIN_GIFT_DIM; w <= MAX_GIFT_DIM; w++ ) {
  124.         for ( l = MIN_GIFT_DIM;l<=MAX_GIFT_DIM; l++) {
  125.             sgasAreasExpected[ w * l] ++;
  126.             sglTotalAreaExpected += w * l;
  127.             sglExpectedCount++;
  128.     }    }
  129.  
  130.     MyPacker( usNumGifts, (void*)sgalSpace, 
  131.                         pNextPresProc, pStorePresProc );
  132.     
  133.     DisposePtr( (Ptr)sgasAreasSeen );
  134.     DisposePtr( (Ptr)sgasAreasExpected );
  135.     DisposePtr( (Ptr)sgasStack );
  136.     DisposePtr( (Ptr)sgalSpace );
  137. }
  138.  
  139. /*------------------------------------------------------
  140.     Utility routines called by packing routine.
  141.   ------------------------------------------------------*/
  142. Boolean BestPosition( long aalSpace[WID_DIM][LEN_DIM],
  143.                         unsigned short usSpaceRemaining,
  144.                         unsigned short usWidth,
  145.                         unsigned short usLength,
  146.                         short *pusX,
  147.                         short *pusY );
  148.  
  149. int LargestGiftDesired( unsigned short usSpaceLeft, 
  150.                         unsigned short usTotalGifts,
  151.                         unsigned short usGiftsRemaining,
  152.                         unsigned short usWidth,
  153.                         unsigned short usLength );
  154.  
  155. void RecomputeAreas( long aalSpace[WID_DIM][LEN_DIM],
  156.                     unsigned short *pusSpaceRemaining,
  157.                     int iHoleSize );
  158.  
  159.  
  160. /********************************************************
  161.  ********************************************************
  162.         MyPacker()
  163.   ------------------------------------------------------
  164.     
  165.     After getting each present check to see what the 
  166.     expected sizes of the next presents will be and
  167.     pick a largest acceptable size.  If the present
  168.     meets the size requirement then find the best 
  169.     location for it (presents like to sit amoung
  170.     friends or with thier back to the wall!), and 
  171.     store it.
  172.  
  173.   *******************************************************
  174.   *******************************************************/
  175.  
  176. void MyPacker( unsigned short usNumGifts,
  177.                 long aalGiftStorage[WID_DIM][LEN_DIM],
  178.                 NextPresProc pNextPresProc,
  179.                 StorePresProc pStorePresProc )
  180. {
  181.     unsigned short usSpaceRemaining, usGiftsRemaining;
  182.     unsigned short    usWidth, usLength;
  183.     int    iLargestGiftDesired, iArea, i;
  184.     int w, l, iHoleSize;
  185.     short X, Y;
  186.         
  187.     usGiftsRemaining = usNumGifts;
  188.     usSpaceRemaining = WID_DIM * LEN_DIM;
  189.  
  190. /*------------------------------------------------------
  191.     Fill storage array with contiguous area values.
  192.     In the beginning all space is empty and contiguous.
  193.   ------------------------------------------------------*/
  194.     for ( w = 0; w < WID_DIM; w++ )
  195.         for ( l = 0; l < LEN_DIM; l++ )
  196.             aalGiftStorage[w][l] = usSpaceRemaining;    
  197.     
  198. /*------------------------------------------------------
  199.     Get the presents.
  200.   ------------------------------------------------------*/
  201.     while ( usGiftsRemaining ) {
  202.         (pNextPresProc)( &usWidth, &usLength );
  203.         usGiftsRemaining--;
  204.         
  205.         iLargestGiftDesired = LargestGiftDesired( 
  206.                         usSpaceRemaining, usNumGifts, 
  207.                         usGiftsRemaining, 
  208.                         usWidth, usLength );
  209.  
  210.         iArea = usWidth * usLength;
  211.         if ( iArea <= iLargestGiftDesired ) {
  212.         
  213.             if ( BestPosition( aalGiftStorage, 
  214.                             usSpaceRemaining,
  215.                             usWidth, usLength, 
  216.                             &X, &Y ) ) {
  217.         
  218.                 iHoleSize = aalGiftStorage[X][Y];
  219.  
  220. /*------------------------------------------------------
  221.                 Store a gift.
  222.   ------------------------------------------------------*/
  223.                 for ( w = 0; w < usWidth; w++ ) {
  224.                     for ( l = 0; l < usLength; l++ ) {
  225.                         aalGiftStorage[X+w][Y+l] 
  226.                                             = SPACE_USED;
  227.                     }
  228.                 }
  229.                 
  230.                 pStorePresProc( (unsigned short)X, 
  231.                                     (unsigned short)Y );
  232.                 sgsGiftsStored++;
  233.                 
  234.                 if ( sgsLeftmostPresent > X )
  235.                     sgsLeftmostPresent = X;
  236.                 if ( sgsTopmostPresent > Y )
  237.                     sgsTopmostPresent = Y;
  238.                     
  239.                 usSpaceRemaining -= iArea;
  240.                 
  241.                 RecomputeAreas( aalGiftStorage, 
  242.                                 &usSpaceRemaining,
  243.                                         iHoleSize );
  244.             }
  245.         }        
  246.         if ( usSpaceRemaining == 0 ) {
  247. #if PRINTF
  248.             printf( "  Presents stored == %i.", 
  249.                             sgsGiftsStored );
  250. #endif
  251.             return;
  252.         }
  253.     }
  254. #if PRINTF
  255.     printf( "  Presents stored == %i.", 
  256.                     sgsGiftsStored );
  257. #endif
  258. }
  259.  
  260. /*======================================================
  261.     Push() & Pop() implement a stack for the 
  262.     flood fill type algorithm FloodMark to store
  263.     data points on instead of recursing into the heap.
  264.   ------------------------------------------------------*/
  265. Push( unsigned usX, unsigned usY )
  266. {
  267.     sgasStack[sglItemsOnStack] = usX;
  268.     sgasStack[sglItemsOnStack+1] = usY;
  269.     sglItemsOnStack += 2;
  270. }
  271. Boolean Pop( unsigned short *pusX, unsigned short *pusY )
  272. {
  273.     if ( sglItemsOnStack ) {
  274.         sglItemsOnStack -= 2;
  275.         *pusX = sgasStack[sglItemsOnStack];
  276.         *pusY = sgasStack[sglItemsOnStack+1];
  277.         return( TRUE );
  278.     }
  279.     return( FALSE );
  280. }
  281.  
  282. /*======================================================
  283.         FloodMark()
  284.         
  285.     This is an implementation of the well documented
  286.     Floodfill alorithm for fill irregular shapes with
  287.     paint or other such graphically stuff.  Here we
  288.     use it to measure the number of contigious values,
  289.     that match the iValueToMatch, variable,
  290.     in the array.  As it encounters each value it 
  291.     marks it with the flag MEASURING so that we can 
  292.     then go and place the new area value back into 
  293.     those positions.
  294.   ------------------------------------------------------*/
  295. long FloodMark( int iValueToMatch,
  296.                 long aal[WID_DIM][LEN_DIM],
  297.                 unsigned short X, unsigned short Y,
  298.                 Boolean *pbCanFitMinGift )
  299. {
  300.     long lPixelsFilled = 0;
  301.     int iV = iValueToMatch;
  302.     int    l, w;
  303.     Boolean bCanFitMinGift = FALSE;
  304.     
  305.     sglItemsOnStack = 0;
  306.     if ( aal[X][Y] == iV )
  307.         Push( X, Y );
  308.         
  309.     while ( Pop( &X, &Y ) ) {    
  310.         aal[X][Y] = MEASURING;
  311.         lPixelsFilled++;
  312.         
  313.         if ( ! bCanFitMinGift ) {
  314.             if ( X + MIN_GIFT_DIM - 1 > WID_DIM )
  315.                 goto FAILED_MIN_TEST;
  316.             if ( Y + MIN_GIFT_DIM - 1 > LEN_DIM )
  317.                 goto FAILED_MIN_TEST;
  318.             for ( w = 0; w < MIN_GIFT_DIM; w++ )
  319.                 for ( l = 0; l < MIN_GIFT_DIM; l++ ) 
  320.                     if ( aal[X+w][Y+l] == SPACE_USED )
  321.                         goto FAILED_MIN_TEST;
  322.             
  323.             bCanFitMinGift = TRUE;
  324.         }
  325.  
  326. FAILED_MIN_TEST:;        
  327.         if ( Y > 0 && aal[X][Y-1] == iV )
  328.             Push( X, Y-1 );
  329.         if ( Y+1 < LEN_DIM && aal[X][Y+1] == iV )
  330.             Push( X, Y+1 );
  331.         if ( X > 0 && aal[X-1][Y] == iV )
  332.             Push( X-1, Y );
  333.         if ( X+1 < WID_DIM && aal[X+1][Y] == iV )
  334.             Push( X+1, Y );
  335.     }
  336.     *pbCanFitMinGift = bCanFitMinGift;
  337.     return( lPixelsFilled );
  338. }
  339.  
  340. /*======================================================
  341.         RecomputeAreas()
  342.         
  343.     The matrix that holds the current state of stored
  344.     presents contains zeros were presents are located,
  345.     and every other location contains a value that
  346.     describes the area of the contigious region of 
  347.     which it is a part.  After placing a present in an 
  348.     empty region of size X, call this routine with
  349.     iHoleSize = X, so that the area map can be brought
  350.     up to date.
  351.   ------------------------------------------------------*/
  352. void RecomputeAreas( long aalSpace[WID_DIM][LEN_DIM],
  353.                     unsigned short *pusSpaceRemaining,
  354.                         int iHoleSize )
  355. {
  356.     int    i,j,k,l, iSmallest;
  357.     long lArea;
  358.     Boolean bCanFitMinGift;
  359.  
  360.     for ( i = 0; i < WID_DIM; i++ ) {
  361.       for ( j = 0; j < LEN_DIM; j++ ) {
  362.  
  363.         if ( aalSpace[i][j] == iHoleSize ) {
  364.           lArea = FloodMark( iHoleSize, aalSpace, i, j,
  365.                                       &bCanFitMinGift );
  366.           
  367.           if ( ! bCanFitMinGift ) {
  368. /*------------------------------------------------------
  369.     Remove areas smaller than smallest present.
  370.   ------------------------------------------------------*/
  371.             for( k = 0; k < WID_DIM; k++ )
  372.               for ( l = 0; l < LEN_DIM; l++ )
  373.                 if ( aalSpace[k][l] == MEASURING )
  374.                   aalSpace[k][l] = SPACE_USED;
  375.             (*pusSpaceRemaining) -= lArea;
  376.           } else {
  377.             for( k = 0; k < WID_DIM; k++ )
  378.               for ( l = 0; l < LEN_DIM; l++ )
  379.                 if ( aalSpace[k][l] == MEASURING )
  380.                   aalSpace[k][l] = lArea;
  381.           }
  382.         }
  383.       }
  384.     }
  385. }
  386.  
  387. /*======================================================
  388.         NeighborCount()
  389.     
  390.     As we all know presents like lots of friends and
  391.     are agoraphobic, so pack them in tight leaving as
  392.     few exposed surfaces as possible.  Being next to
  393.     a friend is better than a cold wall, but better to
  394.     cover your rear with a wall then leave it out in 
  395.     the open.
  396.   ------------------------------------------------------*/
  397. int NeighborCount( long aalSpace[WID_DIM][LEN_DIM],
  398.                         unsigned short usWidth,
  399.                         unsigned short usLength,
  400.                         unsigned short usX,
  401.                         unsigned short usY )
  402. {
  403.     unsigned short w, l;
  404.     int iNeighbors;
  405.  
  406.     iNeighbors = 0;
  407.  
  408.     if ( usX + usWidth - 1 < sgsLeftmostPresent ) {
  409.         if ( usX == 0 )
  410.             iNeighbors += (LIKES_WALLS * usLength);
  411.         if ( usX+usWidth == WID_DIM )
  412.             iNeighbors += (LIKES_WALLS * usLength);
  413.     } else {
  414.         for ( l = 0; l < usLength; l++ ) {
  415.             if ( usX == 0 )
  416.                 iNeighbors += LIKES_WALLS;
  417.             else if ( aalSpace[usX-1][usY+l] == SPACE_USED )
  418.                 iNeighbors += LIKES_OTHERS;
  419.                 
  420.             if ( usX+usWidth == WID_DIM )
  421.                 iNeighbors += LIKES_WALLS;
  422.             else if ( aalSpace[usX+usWidth][usY+l] == SPACE_USED )
  423.                 iNeighbors += LIKES_OTHERS;
  424.         } 
  425.     }
  426.     
  427.     if ( usY + usLength - 1 < sgsTopmostPresent ) {
  428.         if ( usY == 0 )
  429.             iNeighbors += (LIKES_WALLS * usWidth);
  430.         if ( usY+usLength == LEN_DIM )
  431.             iNeighbors += (LIKES_WALLS * usWidth);
  432.     } else {
  433.         for ( w = 0; w < usWidth; w++ ) {
  434.             if ( usY == 0 )
  435.                 iNeighbors += LIKES_WALLS;
  436.             else if ( aalSpace[usX+w][usY-1] == SPACE_USED )
  437.                 iNeighbors += LIKES_OTHERS;
  438.                 
  439.             if ( usY+usLength == LEN_DIM )
  440.                 iNeighbors += LIKES_WALLS;
  441.             else if ( aalSpace[usX+w][usY+usLength] == SPACE_USED )
  442.                 iNeighbors += LIKES_OTHERS;
  443.         }
  444.     }
  445.     return( iNeighbors );
  446. }
  447.         
  448. /*======================================================
  449.         BestPosition()
  450.         
  451.     Find the "best" position for this size present.
  452.     If the present does not fit then return FALSE.
  453.     Find the smallest open area that can accomadate
  454.     this package then position it so that it is
  455.     adjacent to as many others, or edges, as possible.
  456.   ------------------------------------------------------*/
  457. Boolean BestPosition( long aalSpace[WID_DIM][LEN_DIM],
  458.                         unsigned short usSpaceRemaining,
  459.                         unsigned short usWidth,
  460.                         unsigned short usLength,
  461.                         short *psX,
  462.                         short *psY )
  463. {
  464.     Boolean bFits = FALSE;
  465.     short sX, sY, w, l;
  466.     int iNeighbors;
  467.     long lThisHole;
  468.     long lSmallestHole = 0x7FFFFFFF;
  469.     int    iMostNeighbors = -1;
  470.             
  471. /*------------------------------------------------------
  472.     1st package always to the lower right corner.
  473.   ------------------------------------------------------*/
  474.     if ( sgsGiftsStored == 0 ) {
  475.         *psX = WID_DIM - usWidth;
  476.         *psY = LEN_DIM - usLength;
  477.         return( TRUE );
  478.     }
  479.     
  480. /*------------------------------------------------------
  481.     Check all potential positions for open space.
  482.   ------------------------------------------------------*/
  483.     for ( sX = WID_DIM - usWidth; sX >= 0 ; sX-- ) {
  484.         for ( sY = LEN_DIM - usLength; sY >= 0 ; sY-- ) {
  485.         
  486.             lThisHole = aalSpace[sX][sY];
  487.  
  488.             if ( lThisHole != SPACE_USED
  489.                         && lSmallestHole >= lThisHole ) {
  490.  
  491.                 for ( w = 0; w < usWidth; w++ ) {
  492.                     for ( l = 0; l < usLength; l++ ) {
  493.                         if ( aalSpace[sX+w][sY+l] == 
  494.                                            SPACE_USED ) {
  495.                             sY -= ( usLength - l );
  496.                             sY ++;
  497.                             goto SPACE_NOT_AVAILABLE;
  498.                         }
  499.                     }
  500.                 }
  501.                     
  502. /*------------------------------------------------------
  503.     Count the neighbors, since presents need friends.
  504.   ------------------------------------------------------*/
  505.                 iNeighbors = NeighborCount( aalSpace,
  506.                             usWidth, usLength, sX, sY );
  507.  
  508.                 if ( iNeighbors > iMostNeighbors 
  509.                         || lSmallestHole > lThisHole ) {
  510.                     bFits = TRUE;
  511.                     *psX = sX;
  512.                     *psY = sY;
  513.                     iMostNeighbors = iNeighbors;
  514.                     lSmallestHole = lThisHole;
  515.                 }
  516.             }
  517.             SPACE_NOT_AVAILABLE:;
  518.         }
  519.     }
  520.     return( bFits );
  521. }
  522.  
  523. /*======================================================
  524.         LargestGiftDesired()
  525.         
  526.     To find the largest gift that we wish to accept
  527.     we total all of the areas from smallest to largest
  528.     of the gifts that we expect to get.  When the 
  529.     expected total approaches the space remaining
  530.     we choose that size as the largest gift to accept.
  531.   ------------------------------------------------------*/
  532. int LargestGiftDesired( unsigned short usSpaceLeft,
  533.                         unsigned short usTotalGifts,
  534.                         unsigned short usGiftsRemain,
  535.                         unsigned short usWidth,
  536.                         unsigned short usLength ) 
  537. {
  538.     long    lExpected1000;
  539.     long    lSpcLeft1000;
  540.     long    lRandomModel;
  541.     long    lObserved;
  542.     int        iSize, iMaxSize;
  543.     
  544.     sgsGiftsSeen++;
  545.     if ( usWidth > MAX_GIFT_DIM 
  546.                     || usLength > MAX_GIFT_DIM )
  547.         return( 0 );
  548.         
  549.     sgasAreasSeen[usWidth * usLength] += 1;
  550.         
  551.     if ( usGiftsRemain <= 5 )
  552.         return( usSpaceLeft );
  553.     
  554.     iSize = MIN_GIFT_DIM * MIN_GIFT_DIM - 1;
  555.     iMaxSize = MAX_GIFT_DIM * MAX_GIFT_DIM;
  556.     lExpected1000 = 0;
  557.     lSpcLeft1000 = usSpaceLeft * 1000L;
  558.     
  559.     while ( lExpected1000 + iSize * 3 * 1000L 
  560.                                 <= lSpcLeft1000
  561.                     && iSize <= iMaxSize ) {
  562.         iSize++;
  563.         lRandomModel = 1000L * 
  564.                         sgasAreasExpected[iSize] * iSize;
  565.         lObserved = 1000L * sgasAreasSeen[iSize] * iSize;
  566.         
  567.         if ( lRandomModel || lObserved ) {
  568.             lRandomModel = usGiftsRemain * lRandomModel 
  569.                                 / sglExpectedCount;
  570.             lObserved = usGiftsRemain * lObserved 
  571.                                 / sgsGiftsSeen;
  572.  
  573. /*------------------------------------------------------
  574.     Distribute weight between expected model and 
  575.     observed sizes by the proportion of the totals
  576.     gifts that we have already seen.
  577.   ------------------------------------------------------*/
  578.             lRandomModel *= usGiftsRemain;
  579.             lRandomModel /= usTotalGifts;
  580.             lObserved *= (usTotalGifts-usGiftsRemain);
  581.             lObserved /= usTotalGifts;
  582.             
  583.             lExpected1000 += lObserved + lRandomModel;
  584.         }
  585.     }
  586.     
  587. #if PRINTF
  588.     printf( "<%i-%i>", usSpaceLeft, iSize );
  589. #endif
  590.     return( iSize );
  591. }
  592.